package com.wcj.test;

import com.wcj.linktable.ListNode;

import java.util.List;

/**
 * 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
 * 例如：
 * 给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
 * 给出的链表为1→1→1→2→3, 返回2→3.
 *
 * 要求：空间复杂度 O(n)，时间复杂度 O(n)
 * 进阶：空间复杂度 O(1)，时间复杂度 O(n)
 */
public class 删除有序链表中重复的元素II {

    public ListNode deleteDuplicates (ListNode head) {
        if (head == null){
            return null;
        }
        if (head.next == null){
            return head;
        }
        ListNode resHead = new ListNode(-1);
        ListNode curTail = resHead;
        ListNode slow = head;
        ListNode fast = head.next;
        boolean flag = false;
        while (fast != null){
            if (slow.val == fast.val){
                flag = true;
            }else {
                if (flag){
                    slow = fast;
                    flag = false;
                }else {
                    curTail.next= slow;
                    curTail = curTail.next;
                    slow = slow.next;
                    curTail.next = null;

                }
            }
            fast = fast.next;
        }
        if (slow.next == null){
            curTail.next= slow;
        }
        return resHead.next;
    }
}
